1. Field of the Invention
The present invention relates generally to an apparatus and method for receiving signals in a communication system, and in particular, to an apparatus and method for receiving signals in a communication system using Low Density Parity Check (LDPC) codes.
2. Description of the Related Art
Due to the rapid development of mobile communication systems, there is a need for technology capable of transmitting bulk data approximating the capacity of a wire network even in a wireless network. To meet the increasing demand for a high-speed, high-capacity communication system capable of processing and transmitting various data such as video and wireless data beyond the voice-oriented service, it is essential to increase system transmission efficiency using an appropriate channel coding scheme in order to improve the system performance. However, due to the characteristics of the mobile communication system, it inevitably incurs error during data transmission due to noises, interference and fading according to channel conditions. The error causes a loss of information data.
Accordingly, various error control schemes are used according to channel characteristics in order to improve reliability of the mobile communication system. The most typical error control scheme uses error correction codes.
It is well known that the LDPC code is superior in performance gain to a convolutional code conventionally used for error correction, during high-speed data transmission. The LDPC code is advantageous in that it can efficiently correct an error caused by noises generated in a transmission channel, thereby increasing reliability of the data transmission. In addition, the LDPC code can be decoded using an iterative decoding algorithm base on a sum-product algorithm in a factor graph. Because a decoder for the LDPC code uses the sum-product algorithm-based iterative decoding algorithm, it is less complex than a decoder for the turbo code. In addition, the decoder for the LDPC code is easy to implement with a parallel processing decoder, as compared with the decoder for the turbo code.
The turbo code has good performance approximating a channel capacity limit of Shannon's channel coding theorem, and the LDPC code shows performance having a difference of only about 0.04 [dB] at the channel capacity limit of Shannon's channel coding theorem at a bit error rate (BER) 10−5, using a block size 107. Shannon's channel coding theorem shows that reliable communication is possible only at a data rate not exceeding a channel capacity. However, Shannon's channel coding theorem has proposed no detailed channel coding/decoding method for supporting a data rate up to the maximum channel capacity limit. Generally, although a random code having a very large block size shows performance approximating the channel capacity limit of Shannon's channel coding theorem, when a MAP (Maximum A Posteriori) or ML (Maximum Likelihood) decoding method is used, it is impossible to implement the decoding method because of its heavy calculation load.
Meanwhile, if the LDPC code is expressed with a factor graph, cycles exist in the factor graph, and it is well known that iterative decoding in the factor graph of the LDPC code where cycles exist is not preferred. Also, it has been experimentally proven that the LDPC code has excellent performance through iterative decoding. However, when there are too many short-length cycles in the factor graph, performance degradation is expected. Therefore, continuous research is being conducted to design an LDPC code where there is no short-length cycle.
The LDPC code, proposed by Gallager, is defined by a parity check matrix in which major elements have a value of 0 and minor elements except for the elements having the value of 0 have a non-zero value, e.g., a value of 1. For convenience, it will be assumed herein that a non-zero value is a value of 1.
Because a parity check matrix of the LDPC code has a very small weight, even a block code having a relatively long length can be decoded through iterative decoding. When a block length of its block code is continuously increased, the LPDC code exhibits performance approximating the channel capacity limit of Shannon's channel coding theorem, like the turbo code. Therefore, the next generation communication system tends to positively use the LDPC code as the error correction code. Herein, for example, the next generation communication system is one of IEEE (Institute of Electrical and Electronics Engineers) 802.11n communication system, IEEE 802.16e communication system, and DVB-S2 (Digital Video Broadcasting-Satellite 2) communication system.
LDPC codes belong to the family of linear block codes. The encoder for a rate
      R    C    =      k    n  block code has k information bits denoted by μ=[μ1, . . . , μk] that are encoded into n code bits denoted by x=[x1, . . . , xn], called a codeword. This codeword is generated/encoded by the linear operation x=μ·G, where G is a k by n generator matrix that defines the encoder. The codeword x is said to be in the code set C, which is the set of all codewords for the encoder defined by G. Unless otherwise stated, for simplicity all elements and operations of the encoder/decoder are defined on Galois Field GF(2), other higher dimensional Galois Fields may also be used.
The generator matrix G has a dual matrix H, which is an m=n−k by n parity check matrix. These matrices, G and H, are orthogonal, i.e. G·HT=0. Herein, the “T” represents an transpose operation. The parity check matrix H defines a set of m parity check equations that are useful in the decoding process. The decoder can determine whether a received codeword estimate {tilde over (x)} is a valid codeword x=μ·G in the code set C by computing {tilde over (x)}·HT before decoding the codeword estimate. Hence, {tilde over (x)} is a valid codeword x when {tilde over (x)}·HT=(μ·G)·HT=0, otherwise if {tilde over (x)}·HT≠0 then an error is detected. The decoder should be able to find the closest or the most likely codeword that was transmitted for each received codeword estimate. For more details on decoding of general linear block codes see Shu Lin and Daniel Costello “Error Control Coding: Fundamentals and Applications”, Prentice Hall.
LDPC codes are defined by an m by n sparse parity check matrix in which there is a lower density of ones compared to zeros. In general, the goal is to find a sparse generator matrix and a sparse parity check matrix for encoding and decoding.
These codes lend themselves to iterative decoding structures to realise near-Shannon capacity performance. The impressive performance of LDPC codes is realised by applying soft decision iterative decoding techniques such as the belief propagation (BP) algorithm, that is, sum-product algorithm, as described by Jinghu Chen and Marc P. C. Fossorier, “Decoding Low-Density Parity Check codes with Normalized APP-Based Algorithm”, 2001, IEEE, or Ajay Dholakia et. al, “Capacity-Approaching Codes: Can They Be Applied to the Magnetic Recording Channel?”. IEEE Communications Magazine, pp 122-130, February 2004, and Engling Yeo et. al., “Iterative Decoder Architectures”, IEEE Communication Magazine, pp 132-140, August 2003.
The soft decision iterative decoding schemes based on the BP algorithm work on the concept of bipartite Tanner graphs as described in Frank R Kschischang, “Codes Defined on Graphs”, IEEE Communication Magazine, pp 118-125, August 2003 and Tom Richardson, “The Renaissance of Gallager's Low-Density Parity-Check Codes”, IEEE Communications Magazine, pp 126-131, August 2003.
A bipartite Tanner graph, is a set of graph vertices decomposed into two disjoint sets where these disjoint sets of vertices are a plurality of bit nodes (also called variable nodes or symbol nodes) and a plurality of parity check nodes, hereinafter called check nodes. The graph is bipartite as no two graph vertices within the same set are adjacent. That is, bit nodes are not connected via graph edges to each other, similarly with the check nodes.
Bipartite Tanner graphs are defined by the m by n parity check matrix H. Each bit node is connected via graph edges to a set of check nodes defined by M(i)={j|Hi,j=1} for bit node i, wherein 1≦j≦m, and m is the number of check nodes (or number of rows in H). Similarly, each check node is connected via graph edges to a set of bit nodes defined by N(j)={i|Hi,j=1} for check node j, wherein 1≦i≦n, and n is the number of bit nodes (or the number of columns of H and the number of code bits per codeword).
The iterative decoding algorithms that are based on the concept of bipartite Tanner graphs are called message passing algorithms. Conceptually, these algorithms use the structure of the Tanner graph to “pass” messages, along graph edges, from the bit nodes to check nodes and vice versa. Typically, in implementing an iterative algorithm, the messages can be variables stored in a memory, for example a set of messages for each bit node i that are passed to a set of check nodes can be stored as variables in an array, and operated on as such. The use of the terms, “pass” or “message passing” and the like, are for illustrative purposes to describe the iterative decoding algorithms that follow with reference to Tanner graphs.
The messages are used to iteratively estimate the code bits of the codeword to be estimated. In one iteration of an iterative decoding algorithm, each bit node passes messages, called bit node messages, that represent an estimate of its respective code bit to all neighbouring check nodes (i.e. those check nodes associated/connected with that bit node via edges). Each neighbouring check node also receives from other neighbouring bit nodes additional bit node messages. The neighbouring check nodes passes back to the original bit node a combination of all these bit node messages via messages called check node messages. This process occurs for every bit node, hence each bit node receives a check node message from each of its neighbouring check nodes and can combine these to form an estimate of its respective code bit. Overall, in each iteration an estimate of a codeword is produced.
Although Tanner graphs can operate on messages based in the Galois Field GF(2), in soft decision iterative decoding algorithms these messages typically represent probabilities or log-likelihood ratios thereof. Hence these messages and operations are not limited to being defined on GF(2), but can be defined on other fields such as, for example, the field of real numbers r.
More specifically in terms of LDPC codes, each bit node i passes a set of bit node messages to the set of check nodes M(i), which are used in each check node to update the check node messages. Similarly, each check node j passes a set of check node messages to the set of bit nodes N(j). In each iteration of these algorithms, there are two main processes called the bit node update process, which updates the bit node messages, and the check node update process, which updates the check node messages.
The bit node and check node messages are considered the information obtainable from the received codeword about the transmitted codeword, which is called extrinsic bit node and check node messages (these terms may hereinafter be used interchangeably). In essence, these messages represent the reliability or the belief for the estimate of the n code bits of the transmitted/received codeword.
In the bit node update process, the bit nodes receive a priori information related to the channel, hence in an additive white gaussian noise (AWGN) channel, for example, bit node i receives the log likelihood ratio of the i-th bit of the received code word estimate given by the intrinsic information
            I      i        =                  2                  σ          2                    ⁢              y        i              ,where σ2=N0/2 is the variance of the AWGN and N0/2 is the power spectral density. The intrinsic information
      I    i    =            2              σ        2              ⁢          y      i      is used to initialise the BP algorithm—or for that matter most of the other algorithms as well.
The bit node message that is passed from bit node i to check node j is denoted as Ti,j. This message Ti,j is updated by summing the set of check node messages passed from the set of check nodes M(i) to bit node i, but excluding the check node message passed from check node j to bit node i. This update process requires fewer computational resources (or has a lower complexity) compared with the check node update process.
It is the check node update process that contributes the greatest complexity to the computation of the BP algorithm. The computational burden comes from a non-linear function, Φ(•) (defined below in equation (3)), used in each check node message update.
In the check node update, the check node message that is passed from check node j to bit node i is denoted by Ej,i. Each check node message Ej,i is updated by summing Φ(Ti,j) over the set of bit node messages passed from the set of bit nodes N(j) to check node j, but excluding the bit node message Ti,j passed from bit node i to check node j. Finally, Ej,i is updated by reapplying Φ(•) to the non-linear summation of Φ(Ti,j).
In an attempt to simplify matters, the sign of Ej,i and the magnitude of Ej,i are computed separately. However, it is the magnitude of Ej,i that contributes towards the overall complexity of the check node update process.
The iterations of the BP algorithm continue until either a predetermined or maximum number of iterations is achieved, or until algorithm has converged, that is the bit node messages have converged. A soft decision (denoted Ti) for bit node i is calculated by summing the intrinsic information Ii and the set of check node messages that are passed from the set of check nodes M(i) to bit node i. A hard decision is formed for each of the soft decisions Ti producing zi giving the estimate codeword
            z      _        ~    =            [                        z          1                ,        …        ⁢                                  ,                  z          n                    ]        .  The parity check equations are applied, {tilde over (z)}·HT, to check if the estimated codeword is in error and depending on the error correction capability of the code the codeword can decoded accordingly giving the information estimate
            μ      _        ~    =            [                        μ          1                ,        …        ⁢                                  ,                  μ          k                    ]        .  
The complexity of the decoding process is primarily, due to the non-linear function used in the check node update process. Hence, reducing the complexity of this process is the focus of current research in the field of LDPC Codes. Several examples of reduced complexity LDPC decoders are disclosed in US 2005/0204271 A1 and US 2005/0138519 A1.
A simplified LDPC decoding process is disclosed in US 2005/0204271 A1, which describes an iterative LDPC decoder that uses a “serial schedule” for processing the bit node and check node messages. Schedules are updating rules indicating the order of passing messages between nodes in the Tanner graph. As well, an approximation to the BP algorithm called the Min-Max algorithm is used in the iterative decoding process in order to reduce the complexity of the check node update process.
This is achieved by using a property of the non-linear function, Φ(•), in which small values of Ti,j contribute the most to the summation of Φ(•). So, for each check node j, the smallest magnitude bit node message is selected from the set of bit node messages passed to check node j. Only this bit node message is used in the approximation, for updating check node j. That is the least reliable bit node message is used and the most reliable bit node messages are discarded.
However, although a reduction in complexity is achieved, the result is a dramatic reduction in bit and frame error rate performance compared to the BP algorithm. This is due to the fact that the discarded extrinsic information Ti,j has not been used in the check node update.
US 2005/0138519 A1 discloses an LDPC decoding process that simplifies the iterative BP algorithm by using a reduced set of bit node messages, i.e. a predetermined number, λ>1, of bit node messages from the set of bit nodes N(j) that are passed to check node j are used in the check node update process. Hence, only the bit nodes that pass the bit node messages with the lowest magnitude levels (smallest or least reliable bit node messages) to check node j are identified and used in the check node update process.
The BP algorithm is then applied to this reduced set of bit node messages in the check node update process. This simplification results in what is called the Lambda-Min algorithm, for more details see F. Guilloud, E. Boutillon, J. L. Danger, “Lambda-Min Decoding Algorithm of Regular and Irregular LDPC Codes”, 3nd International Symposium on Turbo Codes and Related Topics, Brest, France, pp 451-454, September 2003. However, there is only a slight decrease in complexity compared with the BP-algorithm, and typically a large gap in the complexity and performance between λ and λ+1 type Lambda-Min algorithms leading to, what is called, poor granularity in terms of both complexity and performance, where a desired performance is not achievable due to computational resources not being available.
Therefore, there is a need for a LDPC decoding scheme capable of reducing a complexity and maintaining a performance.